#include <iostream>
#include <chrono>
#include "BinarySearchTree.h"

using namespace std;

template <typename T>
void PrintVector(const std::vector<T> &_data)
{
    for (auto iter = _data.begin(); iter != _data.end(); iter++)
    {
        cout << *iter << ",";
    }
    cout << endl;
}

int main()
{
    cout << "Testing the result after sorting......" << endl;
    vector<int> test1, test2;
    int test_size = 100;
    cout << "The original vector: ";
    for (int i = 0; i < test_size; i++)
    {
        int tmp = rand() % 200;
        test1.push_back(tmp);
        test2.push_back(tmp);
        cout << tmp << ",";
    }
    cout << endl;
    BST_sort<int>(test1);
    cout << "The vector after BST_sorting: ";
    PrintVector<int>(test1);

    Randomized_BST_sort<int>(test2);
    cout << "The vector after Randomized_BST_sorting: ";
    PrintVector<int>(test2);

    vector<int> v1, v2;
    int NUMS = 40000;
    const int GAP = 3711;

    for (int i = GAP; i != 0; i = (i + GAP) % NUMS)
    {
        v1.push_back(i);
        v2.push_back(i);
    }

    auto start = std::chrono::high_resolution_clock::now();
    BST_sort<int>(v1);
    auto end = std::chrono::high_resolution_clock::now();
    cout << "BST_sort takes " << (end - start).count() / float(1e9) << " seconds." << endl;

    start = std::chrono::high_resolution_clock::now();
    Randomized_BST_sort<int>(v2);
    end = std::chrono::high_resolution_clock::now();
    cout << "Randomized_BST_sort takes " << (end - start).count() / float(1e9) << " seconds." << endl;

    start = std::chrono::high_resolution_clock::now();
    random_shuffle(v1.begin(), v1.end());
    end = std::chrono::high_resolution_clock::now();
    cout << "random_shuffle takes " << (end - start).count() / float(1e9) << " seconds." << endl;
}
